package com.example.lcpractice.recursion;

public class Queue8 {
    public static void main(String[] args) {
        recursion(0);
        System.out.printf("how many to solve: %d",count);
        System.out.println();
    }

    //定义一个max表示共有多少个皇后
    public static int QUEUE_NUM = 8;
    //定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
    public static int[] QUEUE_ARRAY = new int[QUEUE_NUM];
    // how many resolution
    static int count = 0;

    /**
     * <b>最难理解处</b>
     * @param n 方便启动输入0和递归时调n+1
     */
    public static void recursion(int n) {
        if(n == QUEUE_NUM) {  //n = 8 , 其实8个皇后就既然放好
            recordResult();
            return;
        }

        //在一行左列到右列依次放入皇后，并判断是否冲突
        for(int i = 0; i < QUEUE_NUM; i++) {
            //先把当前这个皇后 n , 放到该行的第1列
            QUEUE_ARRAY[n] = i;
            //判断当放置第n个皇后到i列时，是否冲突
            if(isRightPlace(n)) { // 不冲突
                //接着放n+1个皇后,即开始递归
                recursion(n+1); //
            }
            //如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得 后移的一个位置

        }
    }

    /**
     * 判断最近一步是否该皇后是否和前面已经摆放的皇后冲突
     *
     * @param lastStep 最后放皇后是第n步（已经预先放入）
     * @return 不重合-true
     */
    public static boolean isRightPlace(int lastStep) {
        for (int i = 0; i < lastStep; i++) {
            // 1. QUEUE_ARRAY[i] == lastStep, 代表列上重合（序数代表行，不会重合）
            // 2. lastStep - i == QUEUE_ARRAY[lastStep] - QUEUE_ARRAY[i] 代表斜率为1或垂直，即斜线重合
            if (QUEUE_ARRAY[i] == QUEUE_ARRAY[lastStep] ||Math.abs( lastStep - i )==Math.abs( QUEUE_ARRAY[lastStep] - QUEUE_ARRAY[i])) {
                return false;
            }
        }
        return true;
    }


    public static void recordResult() {
        //写一个方法，可以将皇后摆放的位置输出
        count++;
        for (int i = 0; i < QUEUE_ARRAY.length; i++) {
            System.out.print(QUEUE_ARRAY[i] + " ");
        }
        System.out.println();
        //clear arr记住不需要清空数组，通过回溯的方式从8行-》7行-》6行···的树状形式回溯判断不同的组合
//        QUEUE_ARRAY = new int[QUEUE_NUM];
    }
}

